# 思路：按层遍历节点，当该节点既没有左孩子，又没有右孩子，则返回定义的temp值，否则继续遍历
# 叶子节点的定义是：没有子节点
from collections import deque
from tools.treeNode import Tree


def minDepth(root):
    if not root:
        return 0
    q = deque()
    q.append(root)
    res = 1
    while len(q):
        size = len(q)
        while size > 0:
            temp = q.popleft()
            if (not temp.left) and (not temp.right):
                return res
            if temp.left:
                q.append(temp.left)
            if temp.right:
                q.append(temp.right)

            size -= 1
        res += 1
    return 0


root = Tree(1)
root.left = Tree(2)
root.right = Tree(2)
# root.left.left = Tree(3)
# root.left.right = Tree(4)
root.right.left = Tree(4)
root.right.right = Tree(3)
print(minDepth(root))  # 2
